// LongestConsecutive.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
#include <vector>
using namespace std;

void SetBucket(unsigned char *bucket, unsigned int bit){
	int i = bit/8;
	int j = bit%8;
	bucket[i] |= (0x1 << j);
}

bool GetBucket(unsigned char *bucket, unsigned int bit){
	int i = bit/8;
	int j = bit/8;
	return ((bucket[i] & (0x1 << j)) != 0);
}

int longestConsecutive(vector<int> &num) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function

	int length = num.size();
	if(length < 2)
		return length;
	// find max and min
	int max = num[0];
	int min = num[0];
	for(int i=1; i<length; ++i){
		if(num[i]>max)
			max = num[i];
		if(num[i]<min)
			min = num[i];
	}
	// space
	unsigned int delta = max - min + 1;
	unsigned int bucketLength = (delta+(unsigned int)7)/8;
	unsigned char *bucket = new unsigned char[bucketLength];
	for(int i=0; i<bucketLength; ++i)
		bucket[i] = (unsigned char)0;
	// put to bucket
	for(int i=0; i<num.size(); ++i){
		unsigned int temp = num[i];
		SetBucket(bucket, temp-min);
	}
	// linear scan
	int res = 0;
	int begin = 0;
	bool pre = false;
	for(int i=0; i<max-min+1; ++i){
		bool cur = GetBucket(bucket, i);
		if(cur==true && pre==false){
			begin = i;
		}
		else if(cur==false && pre==true){
			int len = i - begin + 1;
			if(len > res)
				res = len;
		}
		pre = cur;
	}
	return res;
}

#include <map>

int longestConsecutive1(vector<int> &num) {
	// insert into map
	map<int, int> board;
	for(int i=0; i<num.size(); ++i){
		board[num[i]] = 0;
	}
	// scan through
	int max = 0;
	for(map<int, int>::iterator it=board.begin();
		it != board.end();
		++it){
		if(it->second != 0)
			continue;
		int size = 1;

		// go left
		int cur = it->first;
		while(board.find(cur-1) != board.end()){
			cur = cur-1;
			board[cur] = 1;
			++size;
		}
		// go right
		cur = it->first;
		while(board.find(cur+1) != board.end()){
			cur = cur + 1;
			board[cur] = 1;
			++size;
		}
		
		if(size > max){
			max = size;
		}
	}
	return max;
}


int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> vec;
	vec.push_back(2147483646);
	vec.push_back(-214748364);
	vec.push_back(0);
	vec.push_back(2);
	vec.push_back(2147483644);
	vec.push_back(-2147483645);
	vec.push_back(2147483645);



	longestConsecutive1(vec);

	return 0;
}

